<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html>
<head>
<!--
    Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
   
    This file is part of the Open-source Dependency Toolkit (OSDT),
    see http://code.google.com/p/open-source-dependency-toolkit. 
 
    The OSDT is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published
    by the Free Software Foundation, either version 3 of the License,
    or (at your option) any later version.

    The OSDT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.
 
    You should have received a copy of the GNU Lesser General Public License
    along with the OSDT in the file COPYING and COPYING.LESSER. If not, see
    http://www.gnu.org/licenses.
-->
</head>
<body bgcolor="white">

<p>Provides classes and interfaces for encoding a graph with node and edge
layers, local features at nodes and edges, local functions with error marking, 
and a base graph. The classes in this package are designed to allow 
efficient recomputation of local functions and error markings after incremental 
graph modifications, ie, after a small number of local changes to a far
bigger base graph.</p>

<h2>Package Specification</h2>

<h3>Layers</h3>

<p>Each graph has an associated set of <i>layers</i> which may be sublayers of
an arbitrary number of other layers; the Graph package is designed so
that the resulting layer structure is always acyclic. A layer can be
thought of as a way of grouping nodes and edges into similarity
classes. All nodes and edges in a graph must belong to a specific layer. 
A layer also specifies the set of features and functions that
are defined at every node and edge in the layer (see below). In
practice, a layer will probably be used exclusively to contain either
nodes (<i>node layers</i>) or edges (<i>edge layers</i>). However, the
Graph package does not prevent nodes and edges from belonging to the
same layer. Each layer must be assigned a unique name. Examples:</p>

<ul>
    <li> <p><b>Dependency trees:</b> A simple dependency tree may be represented as a "word"
    layer that contains all the word nodes in the dependency tree, a
    "dependency" layer that contains all the dependency edges in the tree,
    and a "linearity" layer that contains edges that link a node to its
    preceding node. </p>

    <li> <p><b>Word alignments:</b> A simple many-many word alignment graph may be represented as a
    "source word" layer that contains all source word nodes in the
    alignment, a "target word" layer that contains all target word nodes,
    "linearity" edge layers for source and target nodes, 
    and an "alignment unit" layer where many-many alignment units are
    represented as alignment nodes, which are connected to source and
    target words by means of edges in two edge layers, "source alignment"
    and "target alignment".</p>

    <li> <p><b>Eye-gaze graphs:</b> An eye-gaze graph that encodes how the eye focuses on different words
    in a text during an eye-tracking experiment may be represented as a
    "word" layer that contains all word nodes in the text, a "linearity" 
    edge layer that encodes linear word order, and a "gaze"
    layer that contains all eye-gaze transitions: when the eye lingers at
    a particular word, it is encoded as an edge that starts and ends in
    the same word node; and when the eye moves from one word to another,
    it is encoded as an edge that starts at the first word node and ends
    at the second word node. Each edge contains two features, "t0" and
    "t1", which encode the starting and ending times of the transition.</p>
</ul>

<h3>Local properties (features/functions at nodes/edges/layers)</h3>

<p>Each layer specifies the features and functions that are defined at
all nodes and edges in the layer. Features and functions are collectively referred to
as "Properties", and nodes, edges, and layers are collectively referred to as "Locations". 
A property at a particular location is called a "local property".
A graph allows the assignment of feature-value pairs to any location in the graph. 
Features at nodes and edges must be listed in the set of allowed features for 
the corresponding layer, whereas there are no restrictions on layer features -- ie, 
they do not have to be declared before use.</p>

<h3>Local functions</h3>




<h2>Related Documentation</h2>

<!-- Put @see and @since tags down here. -->

</body>
</html>
